package com.gxc.matrix;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class CalcTime {

    private static final int[][] dir = new int[][]{
            {-1, 0},
            {0, 1},
            {1, 0},
            {0, -1}
    };

    /**
     * @param lights：n*m个街口每个交通灯的周期，值范围[0, 120]，n和m的范围为[1,9]
     * @param timePreRoad：相邻两个街口之间街道的通行时间，范围为[0,600]
     * @param rowStart：起点的行号
     * @param colStart：起点的列号
     * @param rowEnd：终点的行号
     * @param colEnd：终点的列号
     * @return lights[rowStart][colStart] 与 lights[rowEnd][colEnd] 两个街口之间的最短通行时间
     */
    int calcTime(int[][] lights, int timePreRoad, int rowStart, int colStart, int rowEnd, int colEnd){
        int startNum = toNumber(rowStart, colStart, lights);
        int count = lights.length * lights[0].length;
        int[][] mindist = new int[count+1][4];
        for (int i = 0; i < mindist.length; i++) {
            Arrays.fill(mindist[i], Integer.MAX_VALUE);
        }
        mindist[startNum][0]=0;
        mindist[startNum][1]=0;
        mindist[startNum][2]=0;
        mindist[startNum][3]=0;

        boolean[][] visited = new boolean[count+1][4];
        PriorityQueue<Integer[]> queue = new PriorityQueue<>(new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return o1[3] - o2[3];
            }
        });
        queue.add(new Integer[]{1, startNum, 0, 0});

        while (!queue.isEmpty()) {
            Integer[] poll = queue.poll();
            boolean begin = poll[0] == 1;
            int curNum = poll[1];
            int curDir = poll[2];
            if (visited[curNum][curDir]) continue;

            visited[curNum][curDir] = true;
            int[] position = toPosition(curNum, lights);
            int x = position[0];
            int y = position[1];
            for (int k = 0; k < dir.length; k++) {
                if (!begin && curDir == oppositeDir(k)) continue;

                int[] nextDir = dir[k];
                int newX = x + nextDir[0];
                int newY = y + nextDir[1];

                if (newX >=0 && newX<lights.length && newY>=0 && newY<lights[0].length) {
                    int nextNum = toNumber(newX, newY, lights);
                    if (visited[nextNum][k]) continue;

                    int wait = 0;
                    if (!begin) wait = calcWait(curDir, x, y, k, lights);
                    int needTime = wait + timePreRoad;
                    if (needTime + mindist[curNum][curDir] < mindist[nextNum][k]) {
                        mindist[nextNum][k] = needTime + mindist[curNum][curDir];
                        queue.offer(new Integer[]{0, nextNum, k, mindist[nextNum][k]});
                    }
                }
            }
        }
        int endNumber = toNumber(rowEnd, colEnd, lights);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < dir.length; i++) {
            int d = mindist[endNumber][i];
            if (d < min) {
                min = d;
            }
        }
        return min;
    }

    private int calcWait(int curDir, int x, int y, int nextDir, int[][] lights) {
        if ((nextDir + 1) % 4 == curDir) {
            return 0;
        } else {
            return lights[x][y];
        }
    }

    public int oppositeDir(int dir) {
        return (dir + 2) % 4;
    }

    private int[] toPosition(int xy, int[][] lights) {
        int x = xy / lights.length;
        int y = xy % lights.length;
        return new int[]{x, y};
    }

    private int toNumber(int x, int y, int[][] lights) {
        return x * lights.length + y;
    }
}
